package leetcodev1.数组;

public class LeetCode36 {

    //暴力解 根据规则遍历3遍2维数组+3个set（或bitmap）进行存储
    //这道题就是暴力解
    public boolean isValidSudoku1(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    //利用位图节约空间
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] columns = new int[9];
        int[][] subboxes = new int[3][3];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    int flag = 1 << index;
                    if ((rows[i] | flag) == rows[i]) {
                        return false;
                    }

                    if ((columns[i] | flag) == columns[i]) {
                        return false;
                    }

                    if ((subboxes[i / 3][j / 3] | flag) == subboxes[i / 3][j / 3]) {
                        return false;
                    }

                    rows[i] |= flag;
                    columns[i] |= flag;
                    subboxes[i / 3][j / 3] |= flag;
                }
            }
        }
        return true;
    }

}
